package set

// 这个集合使用go语言中映射的特性实现，所以，只有go语言中，允许当作映射key的类型才能使用该集合。比如，不能把切片添加到集合中去，否则会报错。

// New 创建一个集合
func New[T comparable](items ...T) Set[T] {
	st := set[T]{
		elements: make(map[T]bool),
	}

	for _, item := range items {
		st.Add(item)
	}

	return &st
}

// Set 定义set需要哪些方法的接口
type Set[T comparable] interface {
	// Add 添加一个元素到集合
	Add(item T)
	// Len 返回集合元素的个数
	Len() int
	// GetItems 获取集合中的元素，返回一个元素类型为T的数组
	GetItems() []T
	// In 判断元素是否在集合中
	In(item T) bool
	// Delete 删除集合元素
	Delete(item T)
	// IsSubSetOf 检查set是否是set2的子集合
	IsSubSetOf(set2 Set[T]) bool
	// IsProperSubSetOf 判断set是否是set2的真子集  比如: [1,2,3]是[1,2,3,4]的真子集.
	IsProperSubSetOf(set2 Set[T]) bool
	// IsSuperSetOf 判断set是否是set2的超集(父集) 反过来判断子集即可
	IsSuperSetOf(set2 Set[T]) bool
	// IsProperSupersetOf 判断set是否是set2的真父集
	IsProperSupersetOf(set2 Set[T]) bool
	//Union 求合集
	Union(set2 Set[T]) Set[T]
	// Intersection 求交集
	Intersection(set2 Set[T]) Set[T]
	// Difference 求差集
	Difference(set2 Set[T]) Set[T]
	// SymmetricDifference 对称差集
	SymmetricDifference(set2 Set[T]) Set[T]
}

// set 定义一个set结构体
type set[T comparable] struct {
	elements map[T]bool
}

// Add 以下是set结构体实现Set接口的所有方法
func (st *set[T]) Add(value T) {
	st.elements[value] = true
}

func (st *set[T]) Len() int {
	return len(st.elements)
}

func (st *set[T]) GetItems() []T {
	keys := make([]T, 0, len(st.elements))
	for key := range st.elements {
		keys = append(keys, key)
	}
	return keys
}

func (st *set[T]) In(value T) bool {
	if _, in := st.elements[value]; in {
		return true
	}
	return false
}

func (st *set[T]) IsSubSetOf(superSet Set[T]) bool {
	if st.Len() > superSet.Len() {
		return false
	}

	for _, item := range st.GetItems() {
		if !superSet.In(item) {
			return false
		}
	}
	return true
}

func (st *set[T]) Delete(value T) {
	delete(st.elements, value)
}

func (st *set[T]) IsProperSubSetOf(superSet Set[T]) bool {
	/*
		在集合论中，一个集合 A 被称为另一个集合 B 的真子集（proper subset），如果 A 是 B 的子集但 A 不等于 B。
		对于 [1,2,3] 是 [1,2,3,4] 的真子集，这意味着集合 {1,2,3} 是集合 {1,2,3,4} 的子集，但 {1,2,3} 不等于 {1,2,3,4}。
		在符号上，我们通常用 ⊆ 表示子集，而 ⊂ 表示真子集。
	*/
	if st.Len() == superSet.Len() {
		return false
	}
	return st.IsSubSetOf(superSet)
}

func (st *set[T]) IsSuperSetOf(subSet Set[T]) bool {
	return subSet.IsSubSetOf(st)
}

func (st *set[T]) IsProperSupersetOf(subSet Set[T]) bool {
	if st.Len() == subSet.Len() {
		return false
	}
	return st.IsSuperSetOf(subSet)
}

func (st *set[T]) Union(set2 Set[T]) Set[T] {
	unionSet := New[T]()

	for _, item := range st.GetItems() {
		unionSet.Add(item)
	}
	for _, item := range set2.GetItems() {
		unionSet.Add(item)
	}

	return unionSet
}

func (st *set[T]) Intersection(set2 Set[T]) Set[T] {
	intersectionSet := New[T]()
	var minSet, maxSet Set[T]

	if st.Len() > set2.Len() {
		minSet = set2
		maxSet = st
	} else {
		minSet = st
		maxSet = set2
	}

	for _, item := range minSet.GetItems() {
		if maxSet.In(item) {
			intersectionSet.Add(item)
		}
	}

	return intersectionSet
}

func (st *set[T]) Difference(set2 Set[T]) Set[T] {
	differenceSet := New[T]()

	for _, item := range st.GetItems() {
		if !set2.In(item) {
			differenceSet.Add(item)
		}
	}
	return differenceSet
}

func (st *set[T]) SymmetricDifference(set2 Set[T]) Set[T] {
	symmetricDifference := New[T]()
	dropSet := New[T]()

	for _, item := range st.GetItems() {
		if set2.In(item) {
			dropSet.Add(item)
		} else {
			symmetricDifference.Add(item)
		}
	}

	for _, item := range set2.GetItems() {
		if !dropSet.In(item) {
			symmetricDifference.Add(item)
		}
	}

	return symmetricDifference
}
